﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using static System.Net.Mime.MediaTypeNames;

class ListNode21
{
    public int val;

    public ListNode21 next;

    public ListNode21(int val = 0, ListNode21 next = null)
    {
        this.val = val;
        this.next = next;


    }
}

class Sol21
{

    //public ListNode21 MergeList(ListNode21 list1, ListNode21 list2)
    public ListNode21 MergeList2(ListNode21 list1, ListNode21 list2)//迭代法
    {
        if (list1 == null)
        {
            return list2;
        }
        if (list2 == null)
        {
            return list1;
        }

        ListNode21 resHead = new ListNode21();
        ListNode21 res = resHead;
        //在给定的代码中，ListNode21 res 是通过将 resHead 赋值给它来创建的。
        //这种赋值操作实际上是浅拷贝。
        //浅拷贝意味着两个变量 resHead 和 res 指向相同的内存地址，它们引用同一个对象
        //。因此，当 res 移动时，resHead 的指向不会受到影响，它们之间的关系保持不变。
        //例如，如果我们修改 res.next，resHead.next 的值也会相应地发生变化，
        //因为它们引用的是同一个链表节点。
        //下面两种赋值方式的区别
        //ListNode21 res=resHead.next;//res=null,resHead.next=null

        //resHead.next = res;//res.nxet=res






        while (list1 != null && list2 != null)
        {
            if (list1.val < list2.val)
            {
                res.next = list1;

                list1 = list1.next;




            }
            else
            {

                res.next = list2;

                list2 = list2.next;


            }
            res = res.next;//这一步res的引用发生了变化，指向了A或者B，所有resHead不会变化
            //res.next = null;

        }
        if (list1 != null)
        {
            res.next = list1;
        }
        else
        {
            res.next = list2;
        }




        return resHead.next;

    }



    public ListNode21 MergeList(ListNode21 list1, ListNode21 list2)//递归法
    {
        if (list1 == null)
        {
            return list2;
        }
        if (list2 == null)
        {
            return list1;
        }

        ListNode21 res = new ListNode21();
        if (list1.val < list2.val)
        {
            res.next = list1;
            list1 = list1.next;
           
        }
        else
        {
            res.next = list2;
            list2= list2.next;
        }
        res= res.next;
        res.next=MergeList(list1, list2);//这里返回的是后面全部排序好的，挂在后面就行了

        return res;

    }
    }

class Program21
{


    static void Main21(string[] args)
    {
        ListNode21 headA = new ListNode21(1);
        ListNode21 nodeA1 = new ListNode21(2);
        ListNode21 nodeA2 = new ListNode21(4);
        headA.next = nodeA1; nodeA1.next = nodeA2;
        ListNode21 headB = new ListNode21(1);
        ListNode21 nodeB1 = new ListNode21(3);
        ListNode21 nodeB2 = new ListNode21(4);
        headB.next = nodeB1; nodeB1.next = nodeB2;
        Sol21 sol = new Sol21();
        ListNode21 res = sol.MergeList(headA, headB);

        while (res != null)
        {
            Console.WriteLine(res.val);
            res = res.next;
        }
    }
}
